A. Field of the Invention
The present invention generally relates to ternary content-addressable memory. More particularly, the present invention relates to a low-heat, large-scale ternary content-addressable memory using hash. Compression may also be used to further enhance results but is not required.
B. Description of the Related Art
The ability to search records according to data and not address is a well-known problem in databases. Content-addressable memory (CAM), which may also be known as associative memory or associative storage, is a type of memory used for high-speed computer searches. CAMs typically comprise one or more arrays; each array comprises a large number of entries. Each entry, in turn, comprises information to be used in a search or comparison involving one or more input records. One or more input record entries can be compared in parallel.
Information stored in a CAM may be retrieved on the basis of the content rather than the address. A CAM performs comparison (i.e., exclusive-OR or equivalent) operations at the bit level; CAMs fundamentally constitute an array of linked exclusive-OR gates. The results of comparing a group of bits in words or entries in the CAM storage are transmitted to a processing unit as a CAM can be viewed as comprising a number of bit-serial processing elements.
Binary content-addressable memory employs search terms composed entirely of 1s and 0s. Ternary content-addressable memory (TCAM) employs search terms comprising is, 0s, and a third state of “X” or a so-called “Don't Care” bit. The “X” or “Don't Care” bit is a bit whose value is of no relevance to the search being conducted. The X bit is thus determined based on the search interests of the user. TCAMs are used in a number of applications including network routing tables, database engines, data compression, neural networks, intrusion prevention systems, central processing unit (CPU) cache controllers, and translation look-aside buffers.
TCAMs to date have suffered from large use of resources. X bits are typically not eliminated from the searched entries and a TCAM controller searches all TCAM entries or a substantial portion of the TCAM entries. Silicon usage is large due to suboptimal processing of records and entries to remove as much data as possible that is not essential to the search process. Excessive generation of heat has also limited the compactness and speed available.